public class NQueens {
    /**
     * N皇后的问题，常见的是4皇后的问题
     */
    private int[] queens; //用于存储每行皇后的列位置
    private int count; //统计解法的个数

    public NQueens(){
        queens=new int[4];
        count=0;
    }
    public void solveNQueens(){
        backtrack(0);
        System.out.println("总共有 " + count + " 种解法");
    }
    private void printQueens() {
        System.out.println("解法 " + count + ":");
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                if (queens[i] == j) {
                    System.out.print("Q ");
                } else {
                    System.out.print(". ");
                }
            }
            System.out.println();
        }
        System.out.println();
    }

    // 核心是回溯的函数构造
    private void backtrack(int row){
        if(row==4){
            // 此时找到一个解法
            count++;
            printQueens();
        }else{
            for(int col=0;col<4;col++){
                if (isValid(row,col)){
                    queens[row]=col; //在当前行的第col列放置皇后
                    backtrack(row+1);
                }
            }
        }
    }

    // 还需要找到冲突的条件判断，不能同行/列，还有对角线
    private boolean isValid(int row,int col){
        for(int i=0;i<row;i++){ //行
            // queens[i]的值表示的是i行的列位置
            if(queens[i]==col || queens[i]-col ==i-row || queens[i]-col==row-i){
                return false; // 判断是否与之前的皇后冲突
            }
        }
        return true;
    }

    public static void main(String[] args) {
        NQueens nQueens = new NQueens();
        nQueens.solveNQueens();
    }
}
